package com.jxb.five;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 翻转字符串里的单词
 *示例 4：
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 * 示例 5：
 * 输入：s = "Alice does not even like bob"
 * 输出："bob like even not does Alice"
 * @author jiaobo
 * @date Created in 2025/1/3 21:33
 **/
public class ReverseWords_151 {

    public static void main(String[] args) {
        String s = "Alice does not even like bob";
        String s1 = reverseWords(s);
        System.out.println(s1);
    }

    public static String reverseWords(String s) {
        int left = 0,right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        //定义栈
        Deque<String> d = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                //将单词push到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);
            }else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());
        return String.join(" ",d);
    }

    public String reverseWordsWithBack(String s) {
        char[] charArray = s.toCharArray();
        /*left用以排除字符串s开始的空格，最终定位到s中第一个字母*/
        int left = 0;
        /*right用以排除字符串s后面的空格，最终定位到s中最后一个字母
         * 而且right会在s中倒着遍历字符串的单词*/
        int right = charArray.length-1;
        StringBuilder sb = new StringBuilder();
        /*排除字符串s前后空格*/
        while(charArray[left]==' ') left++;
        while(charArray[right] == ' ') right--;

        //倒着遍历字符串
        while (left <= right) {
            int index = right;
            while (index >= left && charArray[index] != ' ') {
                index--;
            }
            //遇见单词前的空格，取出单词
            for (int i = index + 1;i<=right;i++) {
                sb.append(charArray[i]);
            }
            if (index > left) {
                sb.append(" ");
            }
            while (index >= left && charArray[index]==' ') {
                index--;
            }
            right = index;
        }
        return sb.toString();
    }

}
